#include<stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <iostream>

// 队列的链式存储

typedef int ElemType;

typedef struct LinkNode{
    ElemType data;
    struct LinkNode *next;
}LinkNode;

typedef struct{
    LinkNode *front, *rear;
}LinkQueue;

// 初始化
void InitQueue(LinkQueue &q){
    q.front = q.rear=(LinkNode *)malloc(sizeof(LinkNode));
    q.front->next = NULL;
}

// 判断空
bool Empty(LinkQueue q){
    if(q.front = q.rear) return true;
    else return false;
}

// 入队
void EnQueue(LinkQueue &q, ElemType e){
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    s->data=e;
    s->next=NULL;
    // if (q.front == NULL){
    //     q.front = s;  // 在空队列中插入第一个元素
    //     q.rear = s;   // 修改队头队尾指针
    // }else{
    //     q.rear->next=s;
    //     q.rear=s;
    // }
    q.rear->next=s;
    q.rear=s;
}

// 出队
bool DeQueue(LinkQueue &q, ElemType &e){
    if (q.front==q.rear) return false;
    LinkNode *p = q.front->next;
    e = p->data;
    q.front->next = p->next;
    if(q.rear==p) q.rear = q.front;
    free(p);
    return true;
}

